package compile;

import java.util.*;

public class GrammarTransformer {
    private static final int MAXN = 100 + 5;
    private static String[] buf = new String[MAXN]; // 输入产生式
    private static int n; // 产生式的数量
    private static Map<String, Integer> mp = new HashMap<>(); // 记录每个非终结符的下标
    private static List<Node> vnode = new ArrayList<>(); // 每一个非终结符
    private static String start = "S"; // 文法G[s]
    private static boolean[] used = new boolean[MAXN]; // 用于去掉不可达的非终结符

    public static void main(String[] args) {
        init();
        Scanner scanner = new Scanner(System.in);
        System.out.print("请输入文法的产生式个数：");
        n = scanner.nextInt();
        System.out.println("请输入每个产生式，用空格分隔符：");
        for (int i = 0; i < n; i++) {
            buf[i] = scanner.next();
            String[] parts = buf[i].split("->");
            String left = parts[0];
            String right = parts[1];
            if (!mp.containsKey(left)) {
                mp.put(left, vnode.size());
                vnode.add(new Node(left));
            }
            vnode.get(mp.get(left)).push(right);
        }
        eliminateUselessProductions();
        eliminateEpsilonProductions();
        eliminateUnitProductions();
        eliminateLeftRecursion();
        for (Node node : vnode) {
            node.print();
        }
    }

    // 初始化工作
    private static void init() {
        mp.clear();
        vnode.clear();
        start = "S";
        Arrays.fill(used, false);
    }

    // 去掉不可达的非终结符
    private static void eliminateUselessProductions() {
        Queue<String> q = new LinkedList<>();
        q.offer(start);
        used[mp.get(start)] = true;
        while (!q.isEmpty()) {
            String cur = q.poll();
            int idx = mp.get(cur);
            for (String right : vnode.get(idx).right) {
                for (int i = 0; i < right.length(); i++) {
                    if (Character.isUpperCase(right.charAt(i))) {
                        String next = right.substring(i, i + 1);
                        if (!used[mp.get(next)]) {
                            used[mp.get(next)] = true;
                            q.offer(next);
                        }
                    }
                }
            }
        }
        List<Node> newVnode = new ArrayList<>();
        for (Node node : vnode) {
            if (used[mp.get(node.left)]) {
                newVnode.add(node);
            }
        }
        vnode = newVnode;
    }

    // 去掉ε产生式
    private static void eliminateEpsilonProductions() {
        boolean changed = true;
        while (changed) {
            changed = false;
            for (Node node : vnode) {
                if (node.right.contains("ε")) {
                    node.right.remove("ε");
                    if (node.right.isEmpty()) {
                        node.right.add("ε");
                    }
                    for (int i = 0; i < vnode.size(); i++) {
                        Node other = vnode.get(i);
                        if (other.right.contains(node.left)) {
                            other.right.remove(node.left);
                            for (String s : node.right) {
                                other.right.add(s);
                            }
                            changed = true;
                        }
                    }
                }
            }
        }
    }

    // 去掉单一产生式
    private static void eliminateUnitProductions() {
        boolean changed = true;
        while (changed) {
            changed = false;
            for (Node node : vnode) {
                List<String> newRight = new ArrayList<>();
                for (String right : node.right) {
                    if (right.length() == 1 && Character.isUpperCase(right.charAt(0))) {
                        int idx = mp.get(right);
                        for (String s : vnode.get(idx).right) {
                            if (!newRight.contains(s)) {
                                newRight.add(s);
                            }
                        }
                        changed = true;
                    } else {
                        newRight.add(right);
                    }
                }
                node.right = new HashSet<>(newRight);
            }
        }
    }

    // 消除左递归
    private static void eliminateLeftRecursion() {
        for (int i = 0; i < vnode.size(); i++) {
            Node node = vnode.get(i);
            List<String> alpha = new ArrayList<>();
            List<String> beta = new ArrayList<>();
            for (String right : node.right) {
                if (right.startsWith(node.left)) {
                    alpha.add(right.substring(1));
                } else {
                    beta.add(right);
                }
            }
            if (alpha.size() > 0) {
                vnode.remove(i);
                i--;
                Node newNode = new Node(node.left + "'");
                for (String b : beta) {
                    newNode.push(b + node.left + "'");
                }
                for (String a : alpha) {
                    newNode.push(a + node.left + "'|ε");
                }
                vnode.add(newNode);
                for (int j = 0; j < i + 1; j++) {
                    Node other = vnode.get(j);
                    List<String> newRight = new ArrayList<>();
                    for (String right : other.right) {
                        if (right.startsWith(node.left)) {
                            for (String s : newNode.right) {
                                newRight.add(s + right.substring(1));
                            }
                        } else {
                            newRight.add(right);
                        }
                    }
                    other.right = new HashSet<>(newRight);
                }
            }
        }
        // 消除间接左递归
        for (int i = 0; i < vnode.size(); i++) {
            Node node = vnode.get(i);
            for (int j = 0; j < i; j++) {
                Node other = vnode.get(j);
                List<String> newRight = new ArrayList<>();
                for (String right : node.right) {
                    if (right.startsWith(other.left)) {
                        for (String s : other.right) {
                            newRight.add(s + right.substring(1));
                        }
                    } else {
                        newRight.add(right);
                    }
                }
                node.right = new HashSet<>(newRight);
            }
        }
    }

    private static class Node {
        String left; // 非终结符
        Set<String> right; // 产生式右部

        Node(String str) {
            left = str;
            right = new HashSet<>();
        }

        void push(String str) {
            right.add(str);
        }

        void print() {
            System.out.print(left + "->");
            Iterator<String> it = right.iterator();
            System.out.print(it.next());
            while (it.hasNext()) {
                System.out.print("|" + it.next());
            }
            System.out.println();
        }
    }
}
